{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Subtrees With Max Distance Between Cities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #tree #dynamic-programming #bitmask #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #树 #动态规划 #状态压缩 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countSubgraphsForEachDiameter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计子树中城市之间最大距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你 <code>n</code> 个城市，编号为从 <code>1</code> 到 <code>n</code> 。同时给你一个大小为 <code>n-1</code> 的数组 <code>edges</code> ，其中 <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> 表示城市 <code>u<sub>i</sub></code> 和 <code>v<sub>i</sub></code><sub> </sub>之间有一条双向边。题目保证任意城市之间只有唯一的一条路径。换句话说，所有城市形成了一棵 <strong>树</strong> 。</p>\n",
    "\n",
    "<p>一棵 <strong>子树</strong> 是城市的一个子集，且子集中任意城市之间可以通过子集中的其他城市和边到达。两个子树被认为不一样的条件是至少有一个城市在其中一棵子树中存在，但在另一棵子树中不存在。</p>\n",
    "\n",
    "<p>对于 <code>d</code> 从 <code>1</code> 到 <code>n-1</code> ，请你找到城市间 <strong>最大距离</strong> 恰好为 <code>d</code> 的所有子树数目。</p>\n",
    "\n",
    "<p>请你返回一个大小为 <code>n-1</code> 的数组，其中第<em> </em><code>d</code><em> </em>个元素（<strong>下标从 1 开始</strong>）是城市间 <strong>最大距离</strong> 恰好等于 <code>d</code> 的子树数目。</p>\n",
    "\n",
    "<p><strong>请注意</strong>，两个城市间距离定义为它们之间需要经过的边的数目。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/11/p1.png\" style=\"width: 161px; height: 181px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 4, edges = [[1,2],[2,3],[2,4]]\n",
    "<b>输出：</b>[3,4,0]\n",
    "<strong>解释：\n",
    "</strong>子树 {1,2}, {2,3} 和 {2,4} 最大距离都是 1 。\n",
    "子树 {1,2,3}, {1,2,4}, {2,3,4} 和 {1,2,3,4} 最大距离都为 2 。\n",
    "不存在城市间最大距离为 3 的子树。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 2, edges = [[1,2]]\n",
    "<b>输出：</b>[1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 3, edges = [[1,2],[2,3]]\n",
    "<b>输出：</b>[2,1]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 <= n <= 15</code></li>\n",
    "\t<li><code>edges.length == n-1</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>1 <= u<sub>i</sub>, v<sub>i</sub> <= n</code></li>\n",
    "\t<li>题目保证 <code>(u<sub>i</sub>, v<sub>i</sub>)</code> 所表示的边互不相同。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-subtrees-with-max-distance-between-cities](https://leetcode.cn/problems/count-subtrees-with-max-distance-between-cities/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-subtrees-with-max-distance-between-cities](https://leetcode.cn/problems/count-subtrees-with-max-distance-between-cities/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[[1,2],[2,3],[2,4]]', '2\\n[[1,2]]', '3\\n[[1,2],[2,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        def dfs(u: int, d: int = 0):\n",
    "            nonlocal mx, nxt, msk\n",
    "            if mx < d:\n",
    "                mx, nxt = d, u\n",
    "            msk ^= 1 << u\n",
    "            for v in g[u]:\n",
    "                if msk >> v & 1:\n",
    "                    dfs(v, d + 1)\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            u, v = u - 1, v - 1\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        ans = [0] * (n - 1)\n",
    "        nxt = mx = 0\n",
    "        for mask in range(1, 1 << n):\n",
    "            if mask & (mask - 1) == 0:\n",
    "                continue\n",
    "            msk, mx = mask, 0\n",
    "            cur = msk.bit_length() - 1\n",
    "            dfs(cur)\n",
    "            if msk == 0:\n",
    "                msk, mx = mask, 0\n",
    "                dfs(nxt)\n",
    "                ans[mx - 1] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 建树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)  # 编号改为从 0 开始\n",
    "\n",
    "        ans = [0] * (n - 1)\n",
    "        for mask in range(3, 1 << n):  # 二进制枚举所有集合\n",
    "            if mask.bit_count() < 2:  # 至少要2个点\n",
    "                continue\n",
    "\n",
    "            vis = diameter = 0\n",
    "\n",
    "            def dfs(x: int) -> int:  # 从x点出发，求包含x的子树的直径\n",
    "                nonlocal vis, diameter\n",
    "                vis |= 1 << x  # 标识访问\n",
    "                mx_len = 0\n",
    "                for y in g[x]:\n",
    "                    if (1 << y) & mask and (1 << y) & vis == 0:  # y在mask里面但是还未访问过\n",
    "                        ml = dfs(y) + 1\n",
    "                        diameter = max(diameter, mx_len + ml)\n",
    "                        mx_len = max(mx_len, ml)\n",
    "                return mx_len\n",
    "\n",
    "            t = mask\n",
    "            i = 0\n",
    "            while t:  # 从一个在 mask 中的点开始递归\n",
    "                if (t >> i) & 1:\n",
    "                    break\n",
    "                i += 1\n",
    "            dfs(i)\n",
    "            if vis == mask:\n",
    "                ans[diameter - 1] += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 求不同直径下子树的数目\n",
    "        dis = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        g = [[] for _ in range(n)]\n",
    "        for s, e in edges:\n",
    "            g[s - 1].append(e - 1)\n",
    "            g[e - 1].append(s - 1)\n",
    "        \n",
    "        def dfs1(x, fa):\n",
    "            for v in g[x]:\n",
    "                if v == fa: continue\n",
    "                dis[i][v] = dis[i][x] + 1\n",
    "                dfs1(v, x)\n",
    "        for i in range(n):\n",
    "            dfs1(i, -1)\n",
    "\n",
    "        def dfs2(x, fa):\n",
    "            cnt = 1\n",
    "            for v in g[x]:\n",
    "                if v != fa and (di[v] < d or di[v] == d and v > j) and (dj[v] < d or dj[v] == d and v > i):\n",
    "                    cnt *= dfs2(v, x)\n",
    "            if di[x] + dj[x] > d:\n",
    "                cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        ans = [0 for _ in range(n - 1)]\n",
    "        for i, di in enumerate(dis):\n",
    "            for j in range(i + 1, n):\n",
    "                dj = dis[j]\n",
    "                d = di[j]\n",
    "                ans[d - 1] += dfs2(i, -1)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 建树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)  # 编号改为从 0 开始\n",
    "\n",
    "        # 计算树上任意两点的距离\n",
    "        dis = [[0] * n for _ in range(n)]\n",
    "        def dfs(x: int, fa: int) -> None:\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dis[i][y] = dis[i][x] + 1  # 自顶向下\n",
    "                    dfs(y, x)\n",
    "        for i in range(n):\n",
    "            dfs(i, -1)  # 计算 i 到其余点的距离\n",
    "\n",
    "        def dfs2(x: int, fa: int) -> int:\n",
    "            # 能递归到这，说明 x 可以选\n",
    "            cnt = 1  # 选 x\n",
    "            for y in g[x]:\n",
    "                if y != fa and \\\n",
    "                   (di[y] < d or di[y] == d and y > j) and \\\n",
    "                   (dj[y] < d or dj[y] == d and y > i):  # 满足这些条件就可以选\n",
    "                    cnt *= dfs2(y, x)  # 每棵子树互相独立，采用乘法原理\n",
    "            if di[x] + dj[x] > d:  # x 是可选点\n",
    "                cnt += 1  # 不选 x\n",
    "            return cnt\n",
    "        ans = [0] * (n - 1)\n",
    "        for i, di in enumerate(dis):\n",
    "            for j in range(i + 1, n):\n",
    "                dj = dis[j]\n",
    "                d = di[j]\n",
    "                ans[d - 1] += dfs2(i, -1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        res = [0] * (n-1)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x-1].append(y-1)\n",
    "            g[y-1].append(x-1)\n",
    "        in_set = [False] * n\n",
    "\n",
    "        def f(i):\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                dia = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b:\n",
    "                        continue\n",
    "                    \n",
    "                    def dfs(x):\n",
    "                        nonlocal dia\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                dia = max(dia, ml+max_len)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if dia and vis == in_set:\n",
    "                    res[dia-1] += 1\n",
    "                return \n",
    "            f(i+1)\n",
    "\n",
    "            in_set[i] = True\n",
    "            f(i+1)\n",
    "            in_set[i] = False\n",
    "\n",
    "        f(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        G = [[] for i in range(n)]\n",
    "        for a, b in edges:\n",
    "            a -= 1; b -= 1\n",
    "            G[a].append(b)\n",
    "            G[b].append(a)\n",
    "        \n",
    "        ans = [0] * (n - 1)\n",
    "\n",
    "        for mask in range(3, 1 << n):\n",
    "            if mask.bit_count() < 2: continue\n",
    "            \n",
    "            maxLen = 0\n",
    "            def dfs(node):\n",
    "                nonlocal mask, maxLen\n",
    "                max_ = 0\n",
    "                mask &= ~(1 << node)\n",
    "                for ch in G[node]:\n",
    "                    if mask >> ch & 1:\n",
    "                        val = dfs(ch) + 1\n",
    "                        maxLen = max(maxLen, max_ + val)\n",
    "                        max_ = max(max_, val)\n",
    "\n",
    "                        \n",
    "                return max_\n",
    "            \n",
    "            dfs(mask.bit_length() - 1)\n",
    "            \n",
    "            if mask == 0: ans[maxLen - 1] += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        graph = collections.defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        \n",
    "    \n",
    "\n",
    "        \n",
    "        check_mask = 0\n",
    "        def check_connect(node, prev,mask):\n",
    "            nonlocal check_mask\n",
    "\n",
    "            check_mask |= 1<<(node-1)\n",
    "            for x in graph[node]:\n",
    "                if x==prev:\n",
    "                    continue\n",
    "            \n",
    "                if 1<<(x-1) & mask:\n",
    "                    check_connect(x,node,mask)\n",
    "            return \n",
    "        \n",
    "        dist = 0\n",
    "        def dist_dfs(root,prev,mask):\n",
    "            nonlocal dist \n",
    "\n",
    "            max_d, second_max_d = 0,0\n",
    "            for x in graph[root]:\n",
    "                if x==prev or (1<<(x-1) & mask==0):\n",
    "                    continue\n",
    "           \n",
    "                sub_dist = dist_dfs(x,root,mask)\n",
    "                if sub_dist+1>=max_d:\n",
    "                    second_max_d = max_d\n",
    "                    max_d = sub_dist+1\n",
    "                else:\n",
    "                    second_max_d = max(sub_dist+1, second_max_d)\n",
    "            \n",
    "            dist = max(dist,max_d+second_max_d)\n",
    "            return max_d\n",
    "\n",
    "\n",
    "\n",
    "        ans = [0]*(n+1)\n",
    "        for mask in range(1,1<<n):\n",
    "        \n",
    "            check_mask = 0\n",
    "            i = 0\n",
    "            while mask & 1<<i ==0:\n",
    "                i += 1\n",
    "             \n",
    "            check_connect(i+1,-1,mask)\n",
    "            \n",
    "            # it means the subtree is connected\n",
    "            # get the distance\n",
    "            if check_mask==mask:\n",
    "                dist = 0 \n",
    "                dist_dfs(i+1,-1,mask)\n",
    "                ans[dist] += 1\n",
    "\n",
    "\n",
    "        \n",
    "        return ans[1:n]\n",
    "            \n",
    "                    \n",
    "\n",
    "                \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1) # 建树，编号改为从0开始\n",
    "\n",
    "        ans = [0] * (n - 1)\n",
    "        for mask in range(3, 1 << n): # 二进制枚举\n",
    "            if (mask & (mask - 1)) == 0: #需要至少两个点\n",
    "                continue\n",
    "            vis = diameter = 0 # 求树的直径\n",
    "            def dfs(x:int) -> int:\n",
    "                nonlocal vis, diameter\n",
    "                vis |= 1 << x #标记x访问过\n",
    "                max_len = 0\n",
    "                for y in g[x]:\n",
    "                    if (vis >> y & 1) == 0 and mask >> y & 1: # y没有访问过， 且在mask中\n",
    "                        ml = dfs(y) + 1\n",
    "                        diameter = max(diameter, max_len + ml)\n",
    "                        max_len = max(max_len, ml)\n",
    "                return max_len\n",
    "            dfs(mask.bit_length() - 1) # 从一个在mask中的点开始递归\n",
    "            if vis == mask:\n",
    "                ans[diameter - 1] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph = [[] for _ in range(n)]                              # 建图\n",
    "        for u, v in edges:\n",
    "            graph[u - 1].append(v - 1)\n",
    "            graph[v - 1].append(u - 1)\n",
    "\n",
    "        def dfs(mask, u):\n",
    "            nonlocal visited, diameter\n",
    "            visited |= 1 << u                                       # 标记 u 访问过\n",
    "            u_len = 0                                               # u 节点的最大路径长度\n",
    "            for v in graph[u]:                                      # 遍历 u 节点的相邻节点\n",
    "                if (visited >> v) & 1 == 0 and mask >> v & 1:       # v 没有访问过，且在子集中\n",
    "                    v_len = dfs(mask, v)                            # 相邻节点的最大路径长度\n",
    "                    diameter = max(diameter, u_len + v_len + 1)     # 维护最大路径长度\n",
    "                    u_len = max(u_len, v_len + 1)                   # 更新 u 节点的最大路径长度\n",
    "            return u_len\n",
    "        \n",
    "        ans = [0 for _ in range(n - 1)]\n",
    "\n",
    "        for mask in range(3, 1 << n):                               # 二进制枚举子集\n",
    "            if mask & (mask - 1) == 0:                              # 子集至少需要两个点\n",
    "                continue\n",
    "            visited = 0\n",
    "            diameter = 0\n",
    "            u = mask.bit_length() - 1        \n",
    "            dfs(mask, u)                                            # 在子集 mask 中递归求树的直径\n",
    "            if visited == mask:\n",
    "                ans[diameter - 1] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ed = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            ed[edge[0]-1].append(edge[1]-1)\n",
    "            ed[edge[1]-1].append(edge[0]-1)\n",
    "        dis = [[0] * n for _ in range(n)]\n",
    "        def dfs(node, father):\n",
    "            for child in ed[node]:\n",
    "                if child != father:\n",
    "                    dis[root][child] = dis[root][node] + 1\n",
    "                    dfs(child, node)\n",
    "        for root in range(n):\n",
    "            dfs(root, -1)\n",
    "        \n",
    "        def dfss(node, father):\n",
    "            cnt = 1\n",
    "            for child in ed[node]:\n",
    "                if child != father:\n",
    "                    if (dis[child][i] < d or (dis[child][i] == d and child > j)) and (dis[child][j] < d or (dis[child][j] == d and child > i)):\n",
    "                        cnt *= dfss(child, node)\n",
    "            if dis[node][i] + dis[node][j] > d:\n",
    "                cnt += 1\n",
    "            return cnt\n",
    "        \n",
    "        res = [0 for _ in range(n-1)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                d = dis[i][j]\n",
    "                res[d-1] += dfss(i, -1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        adj = [[] for _ in range(n)]\n",
    "        dist = [[float('inf')]* n for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            x = edge[0] - 1\n",
    "            y = edge[1] - 1\n",
    "            adj[x].append(y)\n",
    "            adj[y].append(x)\n",
    "            dist[x][y] = dist[y][x] = 1\n",
    "        for i in range(n):\n",
    "            dist[i][i] = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    if dist[i][j] != float('inf') and dist[i][k] != float('inf'):\n",
    "                        dist[j][k] = min(dist[j][k],dist[j][i] + dist[i][k])\n",
    "\n",
    "        def dfs(u: int, parent: int, x: int, y:int) ->int:\n",
    "            if dist[u][x] > dist[x][y] or dist[u][y] > dist[x][y]:\n",
    "                return 1\n",
    "            if (dist[u][y] == dist[x][y] and u < x) or (dist[u][x] == dist[x][y] and u < y):\n",
    "                return 1\n",
    "            \n",
    "            ret = 1\n",
    "            for v in adj[u]:\n",
    "                if v != parent:\n",
    "                    ret *= dfs(v,u,x,y)\n",
    "            if dist[u][x] + dist[u][y] > dist[x][y]:\n",
    "                    ret += 1\n",
    "            return ret\n",
    "        \n",
    "        ans = [0] * (n - 1)\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                ans[dist[i][j] - 1] += dfs(i,-1,i,j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph=[[] for _ in range(n+1)]\n",
    "        for u,v in edges:\n",
    "            graph[u-1].append(v-1)\n",
    "            graph[v-1].append(u-1)\n",
    "        ans=[0]*(n-1)\n",
    "        in_set=[False]*n\n",
    "        #直接算,肯定不好算\n",
    "        #枚举树的所有子集+树形DP(树的直径)\n",
    "        def f(i):\n",
    "            if i==n:\n",
    "                vis=[False]*n\n",
    "                dis=0\n",
    "                #求解树的直径\n",
    "                for j in range(n):\n",
    "                    if not in_set[j]: continue\n",
    "                    def dfs(x):\n",
    "                        nonlocal dis\n",
    "                        vis[x]=True\n",
    "                        dp=1\n",
    "                        res=[0,0]\n",
    "                        for y in graph[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                nex=dfs(y)\n",
    "                                dp=max(dp,nex+1)\n",
    "                                if nex>res[1]:\n",
    "                                    res[0]=res[1]\n",
    "                                    res[1]=nex\n",
    "                                elif nex>res[0]:\n",
    "                                    res[0]=nex\n",
    "                        dis=max(dis,res[0]+res[1])\n",
    "                        return dp\n",
    "                    dfs(j)\n",
    "                    break\n",
    "                if dis>0 and vis==in_set:\n",
    "                    ans[dis-1]+=1\n",
    "                return\n",
    "            #不选\n",
    "            f(i+1)\n",
    "            #选\n",
    "            in_set[i]=True\n",
    "            f(i+1)\n",
    "            in_set[i]=False\n",
    "        f(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "\n",
    "        ans = [0] * (n - 1)\n",
    "        for mask in range(3, 1 << n):\n",
    "            if (mask & (mask - 1)) == 0:\n",
    "                continue;\n",
    "            vis = diameter = 0\n",
    "            def dfs(x: int) -> int:\n",
    "                nonlocal vis, diameter\n",
    "                vis |= 1 << x\n",
    "                max_len = 0\n",
    "                for y in g[x]:\n",
    "                    if (vis >> y & 1) == 0 and mask >> y & 1:\n",
    "                        ml = dfs(y) + 1\n",
    "                        diameter = max(diameter, max_len + ml)\n",
    "                        max_len = max(max_len, ml)\n",
    "                return max_len\n",
    "            dfs(mask.bit_length() - 1)\n",
    "            if vis == mask:\n",
    "                ans[diameter - 1] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 枚举所有子树\n",
    "        g = [[] for _ in range(n)]\n",
    "        ans = [0 for _ in range(n - 1)]\n",
    "        for s, e in edges:\n",
    "            s, e = s - 1, e - 1\n",
    "            g[s].append(e)\n",
    "            g[e].append(s)\n",
    "        for mask in range(3, 1 << n):\n",
    "            if (mask & (mask - 1)) == 0:\n",
    "                continue\n",
    "            dia = 0\n",
    "            vis = 0\n",
    "            def dfs(x):\n",
    "                nonlocal vis, dia\n",
    "                vis |= (1 << x)\n",
    "                maxn = 0\n",
    "                for v in g[x]:\n",
    "                    if mask & (1 << v) and (not vis & (1 << v)):\n",
    "                        ml = dfs(v) + 1\n",
    "                        dia = max(dia, ml + maxn)\n",
    "                        maxn = max(maxn, ml)\n",
    "\n",
    "                return maxn\n",
    "            dfs(mask.bit_length() - 1) # 获取最高位\n",
    "            \n",
    "            if vis == mask:\n",
    "                ans[dia - 1] += 1\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x-1].append(y-1)\n",
    "            g[y-1].append(x-1)\n",
    "        ans = [0] * (n - 1)\n",
    "        in_set = [False] * n\n",
    "        def f(i):\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "                    def dfs(x):\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                len = dfs(y) + 1\n",
    "                                diameter = max(diameter, len + max_len)\n",
    "                                max_len = max(max_len, len)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter-1] += 1\n",
    "                return\n",
    "\n",
    "            f(i+1)\n",
    "            in_set[i] = True\n",
    "            f(i+1)\n",
    "            in_set[i] = False\n",
    "        \n",
    "        f(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 建树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)  # 编号改为从 0 开始\n",
    "\n",
    "        # 计算树上任意两点的距离\n",
    "        dis = [[0] * n for _ in range(n)]\n",
    "        def dfs(x: int, fa: int) -> None:\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dis[i][y] = dis[i][x] + 1  # 自顶向下\n",
    "                    dfs(y, x)\n",
    "        for i in range(n):\n",
    "            dfs(i, -1)  # 计算 i 到其余点的距离\n",
    "\n",
    "        def dfs2(x: int, fa: int) -> int:\n",
    "            # 能递归到这，说明 x 可以选\n",
    "            cnt = 1  # 选 x\n",
    "            for y in g[x]:\n",
    "                if y != fa and (di[y] < d or di[y] == d and y > j) and (dj[y] < d or dj[y] == d and y > i):  # 满足这些条件就可以选\n",
    "                    cnt *= dfs2(y, x)  # 每棵子树互相独立，采用乘法原理\n",
    "            if di[x] + dj[x] > d:  # x 是可选点\n",
    "                cnt += 1  # 不选 x\n",
    "            return cnt\n",
    "        res = [0] * (n - 1)\n",
    "        for i, di in enumerate(dis):\n",
    "            for j in range(i + 1, n):\n",
    "                dj = dis[j]\n",
    "                d = di[j]\n",
    "                res[d - 1] += dfs2(i, -1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # n个节点的树，返回ans[i]，节点间距离为i的节点对数\n",
    "\n",
    "        g = [[] for _ in range(n)]      # 建树\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)      # 编号改为从0开始\n",
    "\n",
    "        ans = [0] * (n - 1)\n",
    "        in_set = [False] * n\n",
    "\n",
    "        def f(i: int)-> None: # 子树枚举\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "\n",
    "                    def dfs(x: int)-> int:  # 求子树的直径\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return\n",
    "            f(i + 1) # 不选城市i\n",
    "            in_set[i] = True\n",
    "            f(i + 1)\n",
    "            in_set[i] = False   # 回复现场\n",
    "        f(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x-1].append(y-1)\n",
    "            g[y-1].append(x-1)\n",
    "        \n",
    "        ans = [0] * (n - 1)\n",
    "        in_set = [False] * n\n",
    "        def f(i):\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b:\n",
    "                        continue\n",
    "                    # 求树直径\n",
    "                    def dfs(x):\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return\n",
    "            f(i+1)\n",
    "\n",
    "            in_set[i] = True\n",
    "            f(i+1)\n",
    "            in_set[i] = False\n",
    "        \n",
    "        f(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        de = defaultdict(set)\n",
    "\n",
    "        for a, b in edges:\n",
    "            de[a].add(b)\n",
    "            de[b].add(a)\n",
    "\n",
    "        ret = [0] * (n - 1)\n",
    "\n",
    "        def dfs(x, visited, s):\n",
    "            visited.add(x)\n",
    "            d = 0\n",
    "            dia = 0\n",
    "            for y in de[x]:\n",
    "                if y not in visited and y in s:\n",
    "                    yd, ydia = dfs(y, visited, s)\n",
    "\n",
    "                    dia = max(dia, ydia, d + yd + 1)\n",
    "                    d = max(d, yd)\n",
    "\n",
    "            return d + 1, dia\n",
    "\n",
    "        def bt(idx, s):\n",
    "            for x in s:\n",
    "                visited = {x}\n",
    "\n",
    "                _, dia = dfs(x, visited, s)\n",
    "\n",
    "                if len(visited) == len(s) and dia > 1:\n",
    "                    ret[dia - 2] += 1\n",
    "\n",
    "                break\n",
    "            \n",
    "            for i in range(idx, n + 1):\n",
    "                s.add(i)\n",
    "                bt(i + 1, s)\n",
    "                s.remove(i)\n",
    "\n",
    "        bt(1, set())\n",
    "\n",
    "        return ret\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 建树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1) # 编号改为从0开始\n",
    "        \n",
    "        ans = [0] * (n - 1)\n",
    "        in_set = [False] * n\n",
    "        def f(i):\n",
    "            if i == n:\n",
    "                visited = [False] * n\n",
    "                diameter = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "                    def dfs(x):\n",
    "                        nonlocal diameter\n",
    "                        visited[x] = b\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not visited[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(ml, max_len)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and visited == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return \n",
    "            f(i + 1)\n",
    "            in_set[i] = True\n",
    "            f(i + 1)\n",
    "            in_set[i] = False\n",
    "        f(0)\n",
    "        return ans \n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        tree = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            tree[u-1].append(v-1)\n",
    "            tree[v-1].append(u-1)\n",
    "\n",
    "        ans = [0] * (n-1)\n",
    "        in_set = [False] * n\n",
    "        \n",
    "        def f(i):\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "                    #find tree diameter\n",
    "                    def dfs(x):\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in tree[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, ml + max_len)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len \n",
    "                    \n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return \n",
    "            \n",
    "            f(i+1)\n",
    "\n",
    "            in_set[i] = True\n",
    "            f(i+1)\n",
    "            in_set[i] = False\n",
    "        f(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        idx = 1\n",
    "        he = [-1] * (n + 7)\n",
    "        e, ne = [-1] * (2 * n + 7), [-1] * (2 * n + 7)\n",
    "\n",
    "        def add(a, b):\n",
    "            nonlocal idx\n",
    "            e[idx] = b\n",
    "            ne[idx] = he[a]\n",
    "            he[a] = idx\n",
    "            idx += 1\n",
    "\n",
    "        for a, b in edges:\n",
    "            add(a, b)\n",
    "            add(b, a)\n",
    "        cnt = [0] * (n - 1)\n",
    "        vis = defaultdict(bool)\n",
    "        nodes = set()\n",
    "        dis = 0\n",
    "\n",
    "        def dfs(a, nodes):\n",
    "            res = 1\n",
    "            i = he[a]\n",
    "            vis[a] = True\n",
    "            while i != -1:\n",
    "                b = e[i]\n",
    "                if not vis[b] and b in nodes:\n",
    "                    res += dfs(b, nodes)\n",
    "                i = ne[i]\n",
    "            return res\n",
    "\n",
    "        def is_valid(mask):\n",
    "            i = 1\n",
    "            while mask:\n",
    "                if mask % 2:\n",
    "                    nodes.add(i)\n",
    "                i += 1\n",
    "                mask = mask >> 1\n",
    "            root = nodes.pop()\n",
    "            m = dfs(root, nodes)\n",
    "            return root, nodes, m == len(nodes) + 1 and m > 1\n",
    "\n",
    "\n",
    "        def get_dis(a, nodes):\n",
    "            nonlocal dis\n",
    "            i = he[a]\n",
    "            vis[a] = True\n",
    "            while i != -1:\n",
    "                b = e[i]\n",
    "                if not vis[b] and b in nodes:\n",
    "                    get_dis(b, nodes)\n",
    "                    dis = max(dis, d[a] + 1 + d[b])\n",
    "                    d[a] = max(d[a], d[b] + 1)\n",
    "                i = ne[i]\n",
    "\n",
    "        d = Counter()\n",
    "\n",
    "        for mask in range(1, 1 << n):\n",
    "            root, nodes, flag = is_valid(mask)\n",
    "            vis.clear()\n",
    "            dis = 0\n",
    "            if flag:\n",
    "                get_dis(root, nodes)\n",
    "                vis.clear()\n",
    "                d.clear()\n",
    "                cnt[dis - 1] += 1   \n",
    "            nodes.clear()\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "    # bit\n",
    "        ans = [0] * (n - 1)\n",
    "        g=[[] for _ in range(n)]\n",
    "        for i in range(len(edges)):\n",
    "            a,b=edges[i]\n",
    "            a-=1\n",
    "            b-=1\n",
    "            edges[i]=[a,b]\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        for i in range(1, 1 << n):\n",
    "            p = []\n",
    "            for j in range(n):\n",
    "                if ((1 << j) | i) == i:\n",
    "                    p.append(j)\n",
    "            # connect?\n",
    "            if len(p) > 1:\n",
    "                visit = 1 << p[0]\n",
    "                bfs = [p[0]]\n",
    "                while bfs:\n",
    "                    nbfs = []\n",
    "                    for c in bfs:\n",
    "                        for a in g[c]:\n",
    "                            if a in p and (visit | (1 << a)) != visit:\n",
    "                                visit |= (1 << a)\n",
    "                                nbfs.append(a)\n",
    "                    bfs = nbfs\n",
    "                if visit == i:\n",
    "                    # distance?\n",
    "                    cd = {}\n",
    "                    for item in p:\n",
    "                        degree = 0\n",
    "                        for con in g[item]:\n",
    "                            if con in p:\n",
    "                                degree += 1\n",
    "                        cd[item] = degree\n",
    "                    r = 0\n",
    "                    while len(cd) > 1:\n",
    "                        remove = []\n",
    "                        for k, v in cd.items():\n",
    "                            if v == 1:\n",
    "                                remove.append(k)\n",
    "                        for rm in remove:\n",
    "                            for con in g[rm]:\n",
    "                                if con in cd:\n",
    "                                    cd[con] -= 1\n",
    "                            del cd[rm]\n",
    "                        r += 1\n",
    "                    dis = r * 2\n",
    "                    if len(cd) == 0:\n",
    "                        dis -= 1\n",
    "                    ans[dis-1] += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x-1].append(y-1)\n",
    "            g[y-1].append(x-1)\n",
    "\n",
    "        ans = [0] * (n-1)\n",
    "        in_set = [False] * n\n",
    "        def f(i):\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "                for v,b in enumerate(in_set):\n",
    "                    if not b:\n",
    "                        continue\n",
    "                    def dfs(x):\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                cur_len = dfs(y) + 1\n",
    "                                diameter = max(diameter, cur_len + max_len)\n",
    "                                max_len = max(max_len, cur_len)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return\n",
    "        \n",
    "            f(i+1)\n",
    "\n",
    "            in_set[i] = True\n",
    "            f(i+1)\n",
    "            in_set[i] = False\n",
    "        f(0)\n",
    "        return ans\n",
    "\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 建树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "\n",
    "        ans = [0] * (n - 1)\n",
    "\n",
    "        # 标记是否选择该节点\n",
    "        in_set = [False] * n  \n",
    "        \n",
    "        def f(i: int) -> None:\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0  # 直径\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "\n",
    "                    # 求树的直径\n",
    "                    def dfs(x: int) -> int:\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    \n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return\n",
    "            \n",
    "            # 不选择节点i\n",
    "            f(i + 1)\n",
    "\n",
    "            # 选择节点i\n",
    "            in_set[i] = True\n",
    "            f(i + 1)\n",
    "            in_set[i] = False\n",
    "    \n",
    "        f(0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    做本题需要弄清楚两点：\n",
    "    1.最大距离就是求一棵树的最大直径（最大的子树边数，不是节点数）\n",
    "    2.如果把所有的合法子树都判断好\n",
    "    第一点比较容易，可以参考：https://leetcode.cn/problems/tree-diameter/\n",
    "    第二点根据题目给出的信息节点数1 - n，n的范围在2 - 15，所以可以用状态压缩，用整形mask表示子树中包含有哪些\n",
    "    节点，对应位置为1表示存在对应下标值的节点，0表示不存在对应下标值的节点\n",
    "    '''\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            graph[u - 1].append(v - 1)\n",
    "            graph[v - 1].append(u - 1)\n",
    "        \n",
    "        ans = [0] * (n - 1)\n",
    "        '''\n",
    "        外层枚举所有的节点组合，要有直径最少要有2个节点，对应mask从3开始\n",
    "        '''\n",
    "        for mask in range(3, 1 << n):\n",
    "            '''\n",
    "            如果有只有一个1，那么mask & mask - 1一定是0，这种方式能过滤掉只有一个1的情况\n",
    "            '''\n",
    "            if not (mask & (mask - 1)):\n",
    "                continue\n",
    "\n",
    "            vis, diameter = 0, 0\n",
    "            '''\n",
    "            以u节点为根节点，计算该子树的最长直径，此时可能mask对应的节点并不能组成一颗合法的树，\n",
    "            比如例1中只选择了1、3、4三个节点，对于这种情况，其实从任意一点往下走，都不可能走完整颗\n",
    "            树，所以用变量vis记录走过的所有节点，最终vis == mask说明当前选择的树是联通的\n",
    "            '''\n",
    "            def helper(u):\n",
    "                nonlocal vis, mask, diameter\n",
    "                vis |= 1 << u\n",
    "                mx, smx = 0, 0\n",
    "                for v in graph[u]:\n",
    "                    if vis & (1 << v) or not (mask & (1 << v)):\n",
    "                        continue\n",
    "                    res = helper(v) + 1\n",
    "                    if res > mx:\n",
    "                        smx = mx\n",
    "                        mx = res \n",
    "                    elif res > smx:\n",
    "                        smx = res\n",
    "                    \n",
    "                    diameter = max(diameter, mx + smx)\n",
    "                return mx\n",
    "            '''\n",
    "            bit_length()表示二进制第一个1是第几位数，从低位到高位算（右到左），减一就等于第一位从0开始的下标，\n",
    "            正好就是选择了一个节点\n",
    "            '''\n",
    "            helper(mask.bit_length() - 1)\n",
    "            if vis == mask:\n",
    "                ans[diameter - 1] += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        e = defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            u -= 1\n",
    "            v -= 1\n",
    "            e[u].add(v)\n",
    "            e[v].add(u)\n",
    "        \n",
    "        def getv(ns):\n",
    "            nonlocal e\n",
    "            v1 = -1\n",
    "            tp1 = -1\n",
    "            def dfs1(cur,fa,d):\n",
    "                nonlocal v1,tp1\n",
    "                if d > v1:\n",
    "                    v1 = d\n",
    "                    tp1 = cur\n",
    "                for nxt in e[cur]:\n",
    "                    if nxt != fa and nxt in ns:\n",
    "                        dfs1(nxt,cur,d + 1)\n",
    "                return\n",
    "            c = -1\n",
    "            for j in ns:\n",
    "                c = j\n",
    "                break\n",
    "            dfs1(c,-1,0)\n",
    "            tp2 = -1\n",
    "            v2 = -1\n",
    "            def dfs2(cur,fa,d):\n",
    "                nonlocal tp2,v2\n",
    "                if d > v2:\n",
    "                    v2 = d\n",
    "                    tp2 = cur\n",
    "                for nxt in e[cur]:\n",
    "                    if nxt != fa and nxt in ns:\n",
    "                        dfs2(nxt,cur,d + 1)\n",
    "                return\n",
    "            dfs2(tp1,-1,0)\n",
    "            return v2\n",
    "        \n",
    "        def getgraph(s):\n",
    "            G = set()\n",
    "            for i in range(n):\n",
    "                if s & (1 << i):\n",
    "                    G.add(i)\n",
    "            return G\n",
    "        \n",
    "        def valid(ns):\n",
    "            nonlocal e\n",
    "            vis = set()\n",
    "            q = deque()\n",
    "            c = -1\n",
    "            for j in ns:\n",
    "                c = j\n",
    "                break\n",
    "            vis.add(c)\n",
    "            q.append(c)\n",
    "            while q:\n",
    "                cur = q.popleft()\n",
    "                for nxt in e[cur]:\n",
    "                    if nxt not in vis and nxt in ns:\n",
    "                        vis.add(nxt)\n",
    "                        q.append(nxt)\n",
    "            return vis == ns\n",
    "        ans = [0 for _ in range(n)]\n",
    "        for i in range(1 << n):\n",
    "            g = getgraph(i)\n",
    "            if valid(g):\n",
    "                t = getv(g)\n",
    "                ans[t] += 1\n",
    "        return ans[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "        ans = [0] * (n - 1)\n",
    "        \n",
    "        for i in range(3, 1 << n):\n",
    "            \n",
    "            mask = i;vis = 0\n",
    "            d = 0\n",
    "            if (mask & (mask - 1)) == 0:continue\n",
    "            def dfs(u):\n",
    "                nonlocal mask,vis,d\n",
    "                vis |= (1<<u)\n",
    "                u_len = 0\n",
    "                for w in g[u]:\n",
    "                    if (vis>>w&1) == 0 and mask>>w&1:\n",
    "                        w_len = dfs(w) + 1\n",
    "                        d = max(w_len+u_len,d)\n",
    "                        u_len = max(u_len,w_len)\n",
    "\n",
    "                return u_len\n",
    "            dfs(mask.bit_length() - 1)\n",
    "            if vis == mask:\n",
    "                ans[d-1] += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        G = defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            G[a].append(b)\n",
    "            G[b].append(a)\n",
    "        \n",
    "        Res = [0] * (n-1)\n",
    "        for i in range(1,2**16):\n",
    "            L,cnt,pos = [],0,0\n",
    "            while (1 << pos) <= i:\n",
    "                if (i >> pos) & 1:\n",
    "                    L.append(pos)\n",
    "                    cnt += 1\n",
    "                pos += 1\n",
    "            S = set(L)\n",
    "            def dc(cur,par):\n",
    "                nonlocal cnt\n",
    "                cnt -= 1\n",
    "                for nxt in G[cur]:\n",
    "                    if nxt == par or nxt not in S:continue\n",
    "                    dc(nxt,cur)\n",
    "                return\n",
    "            dc(L[0],-1)\n",
    "            if cnt or len(L) == 1:continue\n",
    "            v = -1\n",
    "            def dfs(cur,par):\n",
    "                nonlocal v\n",
    "                q = []\n",
    "                for nxt in G[cur]:\n",
    "                    if nxt == par or nxt not in S:continue\n",
    "                    a,b = dfs(nxt,cur)\n",
    "                    heappush(q,-a-1)\n",
    "                if not q:x,y = 0,0\n",
    "                elif len(q) == 1:x,y = q[0],0\n",
    "                else:\n",
    "                    x = heappop(q)\n",
    "                    y = heappop(q)\n",
    "                v = max(v,-x-y+1)\n",
    "                return -x,-y\n",
    "            dfs(L[0],-1)\n",
    "            Res[v-2] += 1\n",
    "        return Res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "       g = [[] for _ in range(n)]\n",
    "       for a, b in edges:\n",
    "          g[a - 1].append(b - 1)\n",
    "          g[b - 1].append(a - 1)\n",
    "       res = [0] * (n - 1)\n",
    "       m = 0\n",
    "       cal = 0\n",
    "       d = 0\n",
    "       def check_tree(x: int, fa: int) -> None:\n",
    "          nonlocal cal \n",
    "          cal |= 1 << x\n",
    "          for y in g[x]:\n",
    "             if y != fa and ((m >> y) & 1) == 1:\n",
    "                check_tree(y, x)\n",
    "       def dfs(x: int, fa: int) -> int:\n",
    "          pre = 0\n",
    "          for y in g[x]:\n",
    "             if y != fa and ((m >> y) & 1) == 1:\n",
    "                cur = dfs(y, x) + 1\n",
    "                nonlocal d\n",
    "                d = max(d, cur + pre)\n",
    "                pre = max(pre, cur)\n",
    "          return pre\n",
    "          \n",
    "       for i in range(1 << n):\n",
    "          if i.bit_count() <= 1:\n",
    "             continue\n",
    "          m = i\n",
    "          cal = 0\n",
    "          d = 0\n",
    "          check_tree((i & -i).bit_length() - 1, -1)\n",
    "          if cal != m:\n",
    "             continue\n",
    "          dfs((i & -i).bit_length() - 1, -1)\n",
    "          res[d - 1] += 1\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            graph[u - 1].append(v - 1)\n",
    "            graph[v - 1].append(u - 1)\n",
    "        \n",
    "        ans = [0] * (n - 1)\n",
    "\n",
    "        for mask in range(3, 1 << n):\n",
    "            if not (mask & (mask - 1)):\n",
    "                continue\n",
    "\n",
    "            vis, diameter = 0, 0\n",
    "\n",
    "            def helper(u):\n",
    "                nonlocal vis, mask, diameter\n",
    "                vis |= 1 << u\n",
    "                mx, smx = 0, 0\n",
    "                for v in graph[u]:\n",
    "                    if vis & (1 << v) or not (mask & (1 << v)):\n",
    "                        continue\n",
    "                    res = helper(v) + 1\n",
    "                    if res > mx:\n",
    "                        smx = mx\n",
    "                        mx = res \n",
    "                    elif res > smx:\n",
    "                        smx = res\n",
    "                    \n",
    "                    diameter = max(diameter, mx + smx + 1)\n",
    "                return mx\n",
    "            \n",
    "            helper(mask.bit_length() - 1)\n",
    "            if vis == mask and diameter:\n",
    "                ans[diameter - 2] += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        dis=[[float(\"inf\")]*(n) for _  in range(n)]\n",
    "        ad=collections.defaultdict(list)\n",
    "        for s,e in edges:\n",
    "            dis[s-1][e-1]=1\n",
    "            dis[e-1][s-1]=1\n",
    "            #ad[s-1].append(e-1)\n",
    "            #ad[e-1].append(s-1)\n",
    "        for i in range(n):\n",
    "            dis[i][i]=0\n",
    "        for k in range(n):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if i==j==k:\n",
    "                        continue\n",
    "                    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])\n",
    "       # print(dis)\n",
    "\n",
    "        res = [0 for _ in range(n)]\n",
    "        ans=[0]*(n-1)\n",
    "        for state in range(1,1<<n):\n",
    "            e=0\n",
    "            mx=0\n",
    "            for x in range(n-1):\n",
    "                for y in range(x+1,n):\n",
    "                    x1=(1<<x)\n",
    "                 #  print(x,x1)\n",
    "                    y1=(1<<y)\n",
    "                   # print(x1,y1)\n",
    "                    if state&x1==x1 and state&y1==y1:\n",
    "                        if dis[x][y]==1:\n",
    "                            e=e+1\n",
    "                        mx=max(mx,dis[x][y])\n",
    "            cnt=str(bin(state)).count(\"1\")\n",
    "            #print(cnt,e)\n",
    "            if cnt==(e+1) and mx!=0:\n",
    "                ans[mx-1]+=1\n",
    "\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            graph[u - 1].append(v - 1)\n",
    "            graph[v - 1].append(u - 1)\n",
    "        \n",
    "        ans = [0] * (n - 1)\n",
    "\n",
    "        for mask in range(3, 1 << n):\n",
    "            if not (mask & (mask - 1)):\n",
    "                continue\n",
    "\n",
    "            vis, diameter = 0, 0\n",
    "\n",
    "            def helper(u):\n",
    "                nonlocal vis, mask, diameter\n",
    "                vis |= 1 << u\n",
    "                mx, smx = 0, 0\n",
    "                for v in graph[u]:\n",
    "                    if vis & (1 << v) or not (mask & (1 << v)):\n",
    "                        continue\n",
    "                    res = helper(v) + 1\n",
    "                    if res > mx:\n",
    "                        smx = mx\n",
    "                        mx = res \n",
    "                    elif res > smx:\n",
    "                        smx = res\n",
    "                    \n",
    "                    diameter = max(diameter, mx + smx + 1)\n",
    "                return mx\n",
    "            \n",
    "            helper(mask.bit_length() - 1)\n",
    "            if vis == mask:\n",
    "                ans[diameter - 2] += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a-1].append(b-1)\n",
    "            g[b-1].append(a-1)\n",
    "        ans = [0] * (n - 1)\n",
    "        def dfs(u):\n",
    "            nonlocal diameter, vis\n",
    "            vis |= 1 << u\n",
    "            maxLen = 0\n",
    "            for v in g[u]:\n",
    "                if (vis >> v & 1) == 0 and (mask >> v & 1) == 1:\n",
    "                    len = dfs(v) + 1\n",
    "                    diameter = max(diameter, maxLen + len)\n",
    "                    maxLen = max(maxLen, len)\n",
    "            return maxLen\n",
    "\n",
    "        for mask in range(3, 1 << n):\n",
    "            if mask & (mask - 1) == 0: continue\n",
    "            vis = 0\n",
    "            diameter = 0\n",
    "            u = mask.bit_length() - 1\n",
    "            dfs(u)\n",
    "            if vis == mask:\n",
    "                ans[diameter-1] += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "\n",
    "        res = [0] * (n - 1)\n",
    "\n",
    "        inset = [False] * n\n",
    "\n",
    "        def f(i):\n",
    "\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "\n",
    "                for v, b in enumerate(inset):\n",
    "                    if not b: continue\n",
    "\n",
    "                    def dfs(x):\n",
    "                        nonlocal diameter\n",
    "\n",
    "                        vis[x] = True\n",
    "\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and inset[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == inset:\n",
    "                    res[diameter - 1] += 1\n",
    "                return\n",
    "            f(i + 1)\n",
    "\n",
    "            inset[i] = True\n",
    "            f(i + 1)\n",
    "            inset[i] = False\n",
    "        f(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 建树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)  # 编号改为从 0 开始\n",
    "\n",
    "        ans = [0] * (n - 1)\n",
    "        in_set = [False] * n\n",
    "        def f(i: int) -> None:\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "                    # 求树的直径\n",
    "                    def dfs(x: int) -> int:\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return\n",
    "            \n",
    "            # 不选城市 i\n",
    "            f(i + 1)\n",
    "\n",
    "            # 选城市  i\n",
    "            in_set[i] = True\n",
    "            f(i + 1)\n",
    "            in_set[i] = False  # 恢复现场\n",
    "        f(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 建树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)  # 编号改为从 0 开始\n",
    "\n",
    "        ans = [0] * (n - 1)\n",
    "        in_set = [False] * n\n",
    "        def f(i: int) -> None:\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "                    # 求树的直径\n",
    "                    def dfs(x: int) -> int:\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return\n",
    "            \n",
    "            # 不选城市 i\n",
    "            f(i + 1)\n",
    "\n",
    "            # 选城市  i\n",
    "            in_set[i] = True\n",
    "            f(i + 1)\n",
    "            in_set[i] = False  # 恢复现场\n",
    "        f(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph=[[] for _ in range(n+1)]\n",
    "        for u,v in edges:\n",
    "            graph[u-1].append(v-1)\n",
    "            graph[v-1].append(u-1)\n",
    "        ans=[0]*(n-1)\n",
    "        in_set=[False]*n\n",
    "        #直接算,肯定不好算\n",
    "        #枚举子集+树形DP(树的直径)\n",
    "        def f(i):\n",
    "            if i==n:\n",
    "                vis=[False]*n\n",
    "                dis=0\n",
    "                #求解树的直径\n",
    "                for j in range(n):\n",
    "                    if not in_set[j]: continue\n",
    "                    def dfs(x):\n",
    "                        nonlocal dis\n",
    "                        vis[x]=True\n",
    "                        dp=1\n",
    "                        res=[0,0]\n",
    "                        for y in graph[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                nex=dfs(y)\n",
    "                                dp=max(dp,nex+1)\n",
    "                                if nex>res[1]:\n",
    "                                    res[0]=res[1]\n",
    "                                    res[1]=nex\n",
    "                                elif nex>res[0]:\n",
    "                                    res[0]=nex\n",
    "                        dis=max(dis,res[0]+res[1])\n",
    "                        return dp\n",
    "                    dfs(j)\n",
    "                    break\n",
    "                if dis>0 and vis==in_set:\n",
    "                    ans[dis-1]+=1\n",
    "                return\n",
    "            #不选\n",
    "            f(i+1)\n",
    "            #选\n",
    "            in_set[i]=True\n",
    "            f(i+1)\n",
    "            in_set[i]=False\n",
    "        f(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph=[[] for _ in range(n+1)]\n",
    "        for u,v in edges:\n",
    "            graph[u-1].append(v-1)\n",
    "            graph[v-1].append(u-1)\n",
    "        ans=[0]*(n-1)\n",
    "        in_set=[False]*n\n",
    "        #直接算,肯定不好算\n",
    "        #枚举树的所有子集+树形DP(树的直径)\n",
    "        #枚举的时候还需要注意是否是有效的树\n",
    "        def f(i):\n",
    "            if i==n:\n",
    "                vis=[False]*n\n",
    "                dis=0\n",
    "                #求解树的直径\n",
    "                for j in range(n):\n",
    "                    if not in_set[j]: continue\n",
    "                    def dfs(x):\n",
    "                        nonlocal dis\n",
    "                        vis[x]=True\n",
    "                        dp=1\n",
    "                        res=[0,0]\n",
    "                        for y in graph[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                nex=dfs(y)\n",
    "                                dp=max(dp,nex+1)\n",
    "                                if nex>res[1]:\n",
    "                                    res[0]=res[1]\n",
    "                                    res[1]=nex\n",
    "                                elif nex>res[0]:\n",
    "                                    res[0]=nex\n",
    "                        dis=max(dis,res[0]+res[1])\n",
    "                        return dp\n",
    "                    dfs(j)\n",
    "                    break\n",
    "                if dis>0 and vis==in_set:\n",
    "                    ans[dis-1]+=1\n",
    "                return\n",
    "            #不选\n",
    "            f(i+1)\n",
    "            #选\n",
    "            in_set[i]=True\n",
    "            f(i+1)\n",
    "            in_set[i]=False\n",
    "        f(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for E in edges:\n",
    "            g[E[0]-1].append(E[1]-1)\n",
    "            g[E[1]-1].append(E[0]-1)\n",
    "        ans = [0] * (n-1)\n",
    "        in_set = [False]*n\n",
    "\n",
    "        def f(i):\n",
    "            if i == n:\n",
    "                vis = [False]*n\n",
    "                d = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "                    def dfs(x):\n",
    "                        nonlocal d\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                             if not vis[y] and in_set[y]:\n",
    "                                 ml = dfs(y) + 1\n",
    "                                 d = max(d, max_len + ml)\n",
    "                                 max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if d and vis == in_set:\n",
    "                    ans[d-1] += 1\n",
    "                return \n",
    "\n",
    "            f(i+1)\n",
    "\n",
    "            in_set[i] = True\n",
    "            f(i+1)\n",
    "            in_set[i] = False\n",
    "        f(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        dis=[[float(\"inf\")]*(n) for _  in range(n)]\n",
    "        ad=collections.defaultdict(list)\n",
    "        for s,e in edges:\n",
    "            dis[s-1][e-1]=1\n",
    "            dis[e-1][s-1]=1\n",
    "            #ad[s-1].append(e-1)\n",
    "            #ad[e-1].append(s-1)\n",
    "        for i in range(n):\n",
    "            dis[i][i]=0\n",
    "        for k in range(n):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if i==j==k:\n",
    "                        continue\n",
    "                    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])\n",
    "        print(dis)\n",
    "\n",
    "        res = [0 for _ in range(n)]\n",
    "        ans=[0]*(n-1)\n",
    "        for state in range(1,1<<n):\n",
    "            e=0\n",
    "            mx=0\n",
    "            for x in range(n-1):\n",
    "                for y in range(x+1,n):\n",
    "                    x1=(1<<x)\n",
    "                 #  print(x,x1)\n",
    "                    y1=(1<<y)\n",
    "                   # print(x1,y1)\n",
    "                    if state&x1==x1 and state&y1==y1:\n",
    "                        if dis[x][y]==1:\n",
    "                            e=e+1\n",
    "                        mx=max(mx,dis[x][y])\n",
    "            cnt=str(bin(state)).count(\"1\")\n",
    "            #print(cnt,e)\n",
    "            if cnt==(e+1) and mx!=0:\n",
    "                ans[mx-1]+=1\n",
    "\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 建树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)  # 编号改为从 0 开始\n",
    "\n",
    "        ans = [0] * (n - 1)\n",
    "        in_set = [False] * n\n",
    "        def f(i: int) -> None:\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "                    # 求树的直径\n",
    "                    def dfs(x: int) -> int:\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return\n",
    "            \n",
    "            # 不选城市 i\n",
    "            f(i + 1)\n",
    "\n",
    "            # 选城市  i\n",
    "            in_set[i] = True\n",
    "            f(i + 1)\n",
    "            in_set[i] = False  # 恢复现场\n",
    "        f(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "\n",
    "        res = [0] * (n - 1)\n",
    "\n",
    "        inset = [False] * n\n",
    "\n",
    "        def f(i):\n",
    "\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "\n",
    "                for v, b in enumerate(inset):\n",
    "                    if not b: continue\n",
    "\n",
    "                    def dfs(x):\n",
    "                        nonlocal diameter\n",
    "\n",
    "                        vis[x] = True\n",
    "\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and inset[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == inset:\n",
    "                    res[diameter - 1] += 1\n",
    "                return\n",
    "            f(i + 1)\n",
    "\n",
    "            inset[i] = True\n",
    "            f(i + 1)\n",
    "            inset[i] = False\n",
    "        f(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.part = n\n",
    "        return\n",
    "\n",
    "    def find(self, x):\n",
    "        lst = []\n",
    "        while x != self.root[x]:\n",
    "            lst.append(x)\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            x = self.root[x]\n",
    "        for w in lst:\n",
    "            self.root[w] = x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        # 将非根节点的秩赋0\n",
    "        self.size[root_x] = 0\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_root_part(self):\n",
    "        # 获取每个根节点对应的组\n",
    "        part = defaultdict(list)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "\n",
    "    def get_root_size(self):\n",
    "        # 获取每个根节点对应的组大小\n",
    "        size = defaultdict(int)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)] = self.size[self.find(i)]\n",
    "        return size\n",
    "\n",
    "\n",
    "class TreeDiameter:\n",
    "    def __init__(self, dct):\n",
    "        self.n = len(dct)\n",
    "        self.dct = dct\n",
    "        return\n",
    "    \n",
    "    def get_bfs_dis(self, root):\n",
    "        dis = [inf] * self.n\n",
    "        stack = [root]\n",
    "        dis[root] = 0\n",
    "        parent = [-1] * self.n\n",
    "        while stack:\n",
    "            i = stack.pop()\n",
    "            for j, w in self.dct[i]:\n",
    "                if j != parent[i]:\n",
    "                    parent[j] = i\n",
    "                    dis[j] = dis[i] + w\n",
    "                    stack.append(j)\n",
    "        return dis, parent\n",
    "    \n",
    "    def get_diameter_info(self) -> (int, int, List[int], any):\n",
    "        # get tree diameter detail by bfs twice\n",
    "        dis, _ = self.get_bfs_dis(0)\n",
    "        x = dis.index(max(dis))\n",
    "        dis, parent = self.get_bfs_dis(x)\n",
    "        y = dis.index(max(dis))\n",
    "        path = [y]\n",
    "        while path[-1] != x:\n",
    "            path.append(parent[path[-1]])\n",
    "        path.reverse()\n",
    "        return x, y, path, dis[y]\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 模板：枚举子集使用并查集判断连通性再计算树的直径\n",
    "        ans = [0] * n\n",
    "        for state in range(1, 1 << n):\n",
    "            node = [i for i in range(n) if state & (1 << i)]\n",
    "            ind = {num: i for i, num in enumerate(node)}\n",
    "            m = len(node)\n",
    "            dct = [[] for _ in range(m)]\n",
    "            uf = UnionFind(m)\n",
    "            for u, v in edges:\n",
    "                u -= 1\n",
    "                v -= 1\n",
    "                if u in ind and v in ind:\n",
    "                    dct[ind[u]].append([ind[v], 1])\n",
    "                    dct[ind[v]].append([ind[u], 1])\n",
    "                    uf.union(ind[u], ind[v])\n",
    "            if uf.part != 1:\n",
    "                continue\n",
    "            tree = TreeDiameter(dct)\n",
    "            ans[tree.get_diameter_info()[-1]] += 1\n",
    "        return ans[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph=[[] for _ in range(n+1)]\n",
    "        for u,v in edges:\n",
    "            graph[u-1].append(v-1)\n",
    "            graph[v-1].append(u-1)\n",
    "        ans=[0]*(n-1)\n",
    "        in_set=[False]*n\n",
    "        #直接算,肯定不好算\n",
    "        #枚举子集+树形DP(树的直径)\n",
    "        def f(i):\n",
    "            if i==n:\n",
    "                vis=[False]*n\n",
    "                dis=0\n",
    "                #求解树的直径\n",
    "                for j in range(n):\n",
    "                    if not in_set[j]: continue\n",
    "                    def dfs(x):\n",
    "                        nonlocal dis\n",
    "                        vis[x]=True\n",
    "                        dp=1\n",
    "                        res=[0,0]\n",
    "                        for y in graph[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                nex=dfs(y)\n",
    "                                dp=max(dp,nex+1)\n",
    "                                if nex>res[1]:\n",
    "                                    res[0]=res[1]\n",
    "                                    res[1]=nex\n",
    "                                elif nex>res[0]:\n",
    "                                    res[0]=nex\n",
    "                        dis=max(dis,res[0]+res[1])\n",
    "                        return dp\n",
    "                    dfs(j)\n",
    "                    break\n",
    "                if dis>0 and vis==in_set:\n",
    "                    ans[dis-1]+=1\n",
    "                return\n",
    "            #不选\n",
    "            f(i+1)\n",
    "            #选\n",
    "            in_set[i]=True\n",
    "            f(i+1)\n",
    "            in_set[i]=False\n",
    "        f(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * (n-1)\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        def check(path):\n",
    "            vis = set()\n",
    "            if not path:\n",
    "                return\n",
    "            dia = 1\n",
    "            # f(v) to get the diameter of a tree\n",
    "            def f(u):\n",
    "                nonlocal dia\n",
    "                vis.add(u)\n",
    "                maxv = 0\n",
    "                for v in g[u]:\n",
    "                    if v not in vis and v in path:\n",
    "                        cur = f(v)\n",
    "                        dia = max(dia, maxv+ cur + 1)\n",
    "                        maxv = max(maxv, cur)\n",
    "                return maxv + 1\n",
    "            f(path[0])\n",
    "\n",
    "            if vis == set(path)  and dia - 1 >= 1:   \n",
    "                ans[dia-2] +=1\n",
    "        def dfs(i, pre):\n",
    "            if i==n:\n",
    "                check(pre)\n",
    "                return\n",
    "            dfs(i+1,pre)\n",
    "            dfs(i+1,pre+[i])\n",
    "        dfs(0,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        #暴力，枚举选或不选，然后判断选出来的集合是否能够构成子树\n",
    "        g=[[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x-1].append(y-1)\n",
    "            g[y-1].append(x-1)\n",
    "        \n",
    "        nodes=[]\n",
    "        ans=[0]*(n-1)\n",
    "        def dfs(i:int):\n",
    "            if i==-1:\n",
    "                if nodes:\n",
    "                    dist=0\n",
    "                    vis=[False]*n\n",
    "                    def calc(x:int,fa:int):\n",
    "                        nonlocal dist\n",
    "                        vis[x]=True\n",
    "                        x_len=0\n",
    "                        for y in g[x]:\n",
    "                            if y==fa or y not in nodes:\n",
    "                                continue\n",
    "                            y_len=calc(y,x)+1\n",
    "                            dist=max(dist,x_len+y_len)\n",
    "                            x_len=max(x_len,y_len)\n",
    "                        return x_len\n",
    "                    calc(nodes[0],-1)\n",
    "                    for x in nodes:\n",
    "                        if not vis[x]:\n",
    "                            return\n",
    "                    if dist:ans[dist-1]+=1\n",
    "                return\n",
    "            dfs(i-1)\n",
    "            nodes.append(i)   \n",
    "            dfs(i-1)\n",
    "            nodes.pop()\n",
    "        dfs(n-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "\n",
    "        ans = [0] * (n-1)\n",
    "        def check(path):\n",
    "            vis = set()\n",
    "            res  = 0\n",
    "            def dp(u):\n",
    "                nonlocal res\n",
    "                vis.add(u)\n",
    "                maxv = 0\n",
    "                for v in g[u]:\n",
    "                    if v not in vis and v in path:\n",
    "                        cur = dp(v) + 1\n",
    "                        res = max(res, maxv + cur)\n",
    "                        maxv = max(maxv, cur)\n",
    "                return maxv\n",
    "            if path:\n",
    "                dp(path[0])\n",
    "            if res and vis == set(path):\n",
    "                ans[res-1] +=1\n",
    "            \n",
    "\n",
    "        def dfs(i,path):    \n",
    "            if i==n:\n",
    "                check(path)\n",
    "                return\n",
    "            dfs(i+1,path)\n",
    "            dfs(i+1, path + [i])\n",
    "        dfs(0,[])\n",
    "        return ans\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 建树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)  # 编号改为从 0 开始\n",
    "\n",
    "        ans = [0] * (n - 1)\n",
    "        in_set = [False] * n\n",
    "        def f(i: int) -> None:\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "                    # 求树的直径\n",
    "                    def dfs(x: int) -> int:\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return\n",
    "            \n",
    "            # 不选城市 i\n",
    "            f(i + 1)\n",
    "\n",
    "            # 选城市  i\n",
    "            in_set[i] = True\n",
    "            f(i + 1)\n",
    "            in_set[i] = False  # 恢复现场\n",
    "        f(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 建树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)  # 编号改为从 0 开始\n",
    "\n",
    "        ans = [0] * (n - 1)\n",
    "        in_set = [False] * n\n",
    "        def f(i: int) -> None:\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "                    # 求树的直径\n",
    "                    def dfs(x: int) -> int:\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return\n",
    "            \n",
    "            # 不选城市 i\n",
    "            f(i + 1)\n",
    "\n",
    "            # 选城市  i\n",
    "            in_set[i] = True\n",
    "            f(i + 1)\n",
    "            in_set[i] = False  # 恢复现场\n",
    "        f(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for v in edges:\n",
    "            g[v[0] - 1].append(v[1] - 1)\n",
    "            g[v[1] - 1].append(v[0] - 1)\n",
    "        ans = [0] * (n - 1)\n",
    "\n",
    "        is_set = [False] * n\n",
    "\n",
    "        def dfs(i: int) -> None:\n",
    "            if i == n:\n",
    "                is_vis = [False] * n\n",
    "                diameter = 0\n",
    "\n",
    "                for i, v in enumerate(is_set):\n",
    "                    if not v:\n",
    "                        continue\n",
    "\n",
    "                    def f(i: int) -> int:\n",
    "                        pre_max = 0\n",
    "                        is_vis[i] = True\n",
    "                        for j in g[i]:\n",
    "                            if not is_vis[j] and is_set[j]:\n",
    "                                cur_l = f(j) + 1\n",
    "                                nonlocal diameter\n",
    "                                diameter = max(cur_l + pre_max, diameter)\n",
    "                                pre_max = max(cur_l, pre_max)\n",
    "\n",
    "                        return pre_max\n",
    "\n",
    "                    f(i)\n",
    "                    break\n",
    "\n",
    "                if diameter > 0 and is_vis == is_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return\n",
    "\n",
    "            dfs(i + 1)\n",
    "\n",
    "            is_set[i] = True\n",
    "            dfs(i + 1)\n",
    "            is_set[i] = False\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * (n-1)\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        def check(path):\n",
    "            vis = set()\n",
    "            dia = 1\n",
    "            def f(u):\n",
    "                vis.add(u)\n",
    "                maxv = 0\n",
    "                for v in g[u]:\n",
    "                    if v not in vis and v in path:\n",
    "                        cur = f(v)\n",
    "                        nonlocal dia\n",
    "                        dia = max(dia, maxv + cur + 1)\n",
    "                        maxv = max(maxv, cur)\n",
    "                return maxv + 1\n",
    "            if path:\n",
    "                f(path[0])\n",
    "                if vis == set(path) and dia -2 >= 0:\n",
    "                    ans[dia-2] +=1\n",
    "        def dfs(i,pre):\n",
    "            if i == n+1:\n",
    "                check(pre)\n",
    "                return\n",
    "            dfs(i+1,pre)\n",
    "            dfs(i+1,pre+[i])\n",
    "        dfs(1,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        ans = [0] * (n-1)\n",
    "\n",
    "        def check(path):\n",
    "            vis = set()\n",
    "            res  = 0\n",
    "            def dfs2(u):\n",
    "                nonlocal res\n",
    "                vis.add(u)\n",
    "                maxv = 0\n",
    "                for v in g[u]:\n",
    "                    if v not in vis and v in path:\n",
    "                        cur = dfs2(v) + 1\n",
    "                        res = max(res, maxv + cur)\n",
    "                        maxv = max(maxv, cur)\n",
    "                return maxv\n",
    "            if path:\n",
    "                dfs2(path[0])\n",
    "            if res and vis == set(path):\n",
    "                ans[res-1] +=1\n",
    "            \n",
    "\n",
    "        def dfs(i,path):    \n",
    "            if i==n:\n",
    "                check(path)\n",
    "                return\n",
    "            dfs(i+1,path)\n",
    "            dfs(i+1, path + [i])\n",
    "        dfs(0,[])\n",
    "        return ans\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g=collections.defaultdict(list)\n",
    "        for i,j in edges:\n",
    "            g[i-1].append(j-1)\n",
    "            g[j-1].append(i-1)\n",
    "        \n",
    "        ans=[0]*(n-1)\n",
    "        inset=[False]*n\n",
    "        def f(i):\n",
    "            if i==n:\n",
    "                vis=[False]*n\n",
    "                dia=0\n",
    "                for k,v in enumerate(inset):\n",
    "                    if not v:continue\n",
    "                    def dfs(x):\n",
    "                        vis[x]=True\n",
    "                        ml=0\n",
    "                        nonlocal dia\n",
    "                        for j in g[x]:\n",
    "                            if inset[j] and not vis[j]:\n",
    "                                l=dfs(j)+1\n",
    "                                dia=max(dia,ml+l)\n",
    "                                ml=max(ml,l)\n",
    "                        return ml\n",
    "                    dfs(k)\n",
    "                    break\n",
    "                if dia and vis==inset:\n",
    "                    ans[dia-1]+=1\n",
    "                return \n",
    "\n",
    "\n",
    "            f(i+1)\n",
    "            inset[i]=True\n",
    "            f(i+1)\n",
    "            inset[i]=False\n",
    "\n",
    "        f(0)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.part = n\n",
    "        return\n",
    "\n",
    "    def find(self, x):\n",
    "        lst = []\n",
    "        while x != self.root[x]:\n",
    "            lst.append(x)\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            x = self.root[x]\n",
    "        for w in lst:\n",
    "            self.root[w] = x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        # 将非根节点的秩赋0\n",
    "        self.size[root_x] = 0\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_root_part(self):\n",
    "        # 获取每个根节点对应的组\n",
    "        part = defaultdict(list)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "\n",
    "    def get_root_size(self):\n",
    "        # 获取每个根节点对应的组大小\n",
    "        size = defaultdict(int)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)] = self.size[self.find(i)]\n",
    "        return size\n",
    "\n",
    "\n",
    "class TreeDiameter:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def build(dct: List[List[int]]) -> (int, int, List[int], any):\n",
    "        # get tree diameter detail by bfs twice\n",
    "        n = len(dct)\n",
    "        x = y = 0\n",
    "        parent = [-1] * n\n",
    "        dis = [inf] * n\n",
    "        for _ in range(2):\n",
    "            x = y\n",
    "            dis = [inf] * n\n",
    "            stack = [x]\n",
    "            dis[x] = 0\n",
    "            parent = [-1] * n\n",
    "            while stack:\n",
    "                i = stack.pop()\n",
    "                for j, w in dct[i]:\n",
    "                    if j != parent[i]:\n",
    "                        parent[j] = i\n",
    "                        dis[j] = dis[i] + w\n",
    "                        stack.append(j)\n",
    "            y = dis.index(max(dis))\n",
    "\n",
    "        path = [y]\n",
    "        while path[-1] != x:\n",
    "            path.append(parent[path[-1]])\n",
    "        path.reverse()\n",
    "        return x, y, path, dis[y]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 模板：枚举子集使用并查集判断连通性再计算树的直径\n",
    "        ans = [0] * n\n",
    "        for state in range(1, 1 << n):\n",
    "            node = [i for i in range(n) if state & (1 << i)]\n",
    "            ind = {num: i for i, num in enumerate(node)}\n",
    "            m = len(node)\n",
    "            dct = [[] for _ in range(m)]\n",
    "            uf = UnionFind(m)\n",
    "            for u, v in edges:\n",
    "                u -= 1\n",
    "                v -= 1\n",
    "                if u in ind and v in ind:\n",
    "                    dct[ind[u]].append([ind[v], 1])\n",
    "                    dct[ind[v]].append([ind[u], 1])\n",
    "                    uf.union(ind[u], ind[v])\n",
    "            if uf.part != 1:\n",
    "                continue\n",
    "            ans[TreeDiameter().build(dct)[-1]] += 1\n",
    "        return ans[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * (n-1)\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        def check(path):\n",
    "            vis = set()\n",
    "            dia = 1\n",
    "            def f(u):\n",
    "                vis.add(u)\n",
    "                maxv = 0\n",
    "                for v in g[u]:\n",
    "                    if v not in vis and v in path:\n",
    "                        cur = f(v)\n",
    "                        nonlocal dia\n",
    "                        dia = max(dia, maxv +cur + 1)\n",
    "                        maxv = max(maxv, cur)\n",
    "                return maxv + 1\n",
    "            if path:\n",
    "                f(path[0])\n",
    "                if vis == set(path) and dia -1 >= 1:\n",
    "                    ans[dia-2] += 1\n",
    "        def dfs(i, pre):\n",
    "            if i == n:\n",
    "                check(pre)\n",
    "                return \n",
    "            dfs(i+1, pre)\n",
    "            dfs(i+1, pre + [i])\n",
    "        dfs(0, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ans= [0] *  (n-1)\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        def check(path):\n",
    "            vis = set()\n",
    "            dia = 1\n",
    "            def f(u):\n",
    "                maxv = 0\n",
    "                vis.add(u)\n",
    "                for v in g[u]:\n",
    "                    if v not in vis and v in path:\n",
    "                        cur = f(v)\n",
    "                        nonlocal dia\n",
    "                        dia = max(dia, maxv + cur + 1)\n",
    "                        maxv = max(maxv, cur)\n",
    "                return maxv + 1\n",
    "            if path:\n",
    "                f(path[0])\n",
    "                if vis == set(path) and dia - 1 >= 1:\n",
    "                    ans[dia-2] +=1\n",
    "        def dfs(i, pre):\n",
    "            if i==n:\n",
    "                check(pre)\n",
    "                return\n",
    "            dfs(i+1, pre)\n",
    "            dfs(i+1, pre+ [i])\n",
    "        dfs(0,[])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * (n-1)\n",
    "        g =defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        def check(path):\n",
    "            vis = set()\n",
    "            if not path:\n",
    "                return \n",
    "            # get the diameter of a tree\n",
    "            dia = 1\n",
    "            def f(u):\n",
    "                nonlocal dia\n",
    "                vis.add(u)\n",
    "                maxv = 0\n",
    "                for v in g[u]:\n",
    "                    if v not in vis and v in path:\n",
    "                        cur = f(v)\n",
    "                        dia = max(dia, maxv + cur + 1)\n",
    "                        maxv = max(maxv, cur)\n",
    "                return maxv + 1\n",
    "            f(path[0])    \n",
    "            if vis == set(path) and dia -1 >= 1:\n",
    "                ans[dia-2] +=1\n",
    "        def dfs(i,pre):\n",
    "            if i ==n:\n",
    "                check(pre)\n",
    "                return \n",
    "            dfs(i+1, pre)\n",
    "            dfs(i+1, pre+[i])\n",
    "        dfs(0,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ans = [0]*(n-1)\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        def check(path):\n",
    "            dia = 1\n",
    "            vis = set()\n",
    "            if not path:\n",
    "                return\n",
    "            \n",
    "            def f(u):    \n",
    "                vis.add(u)\n",
    "                maxv = 0\n",
    "                for v in g[u]:\n",
    "                    if v not in vis and v in path:\n",
    "                        cur = f(v)\n",
    "                        nonlocal dia\n",
    "                        dia = max(dia, maxv+cur + 1)\n",
    "                        maxv = max(maxv, cur)\n",
    "                return maxv + 1\n",
    "            f(path[0])\n",
    "            if vis == set(path) and dia-1 >= 1:\n",
    "                ans[dia-2] +=1\n",
    "\n",
    "        def dfs(i, pre):\n",
    "            if i==n:\n",
    "                check(pre)\n",
    "                return\n",
    "            dfs(i+1, pre)\n",
    "            dfs(i+1, pre+[i])\n",
    "        dfs(0,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * (n-1)\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        def check(path) :   \n",
    "            vis = set()\n",
    "            dia = 1\n",
    "            def f(u):\n",
    "                vis.add(u)\n",
    "                maxv = 0\n",
    "                for v in g[u]:\n",
    "                    if v not in vis and v in path:\n",
    "                        cur = f(v)\n",
    "                        nonlocal dia\n",
    "                        dia = max(dia, maxv+ cur + 1)\n",
    "                        maxv = max(cur, maxv)\n",
    "                return maxv + 1\n",
    "            if path:\n",
    "                f(path[0])\n",
    "                if vis == set(path) and dia -1 -1>=0:\n",
    "                    ans[dia-2] += 1\n",
    "        # i   [0,n-1]\n",
    "        def dfs(i, pre):\n",
    "            if i== n:\n",
    "                check(pre)\n",
    "                return \n",
    "            dfs(i+1,pre)\n",
    "            dfs(i+1, pre + [i])\n",
    "        dfs(0,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ans = [0]  * (n-1)\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "\n",
    "        def check(path):\n",
    "            dia = 1\n",
    "            vis = set()\n",
    "            def f(u):\n",
    "                vis.add(u)\n",
    "                maxv = 0\n",
    "                for v in g[u]:\n",
    "                    if v not in vis and v in path:\n",
    "                        cur =f(v)\n",
    "                        nonlocal dia\n",
    "                        dia = max(dia, maxv + cur + 1)\n",
    "                        maxv = max(maxv, cur)\n",
    "                return maxv + 1\n",
    "\n",
    "            if path:\n",
    "                f(path[0])\n",
    "                if vis == set(path) and dia-2>=0:\n",
    "                    ans[dia-2] +=1\n",
    "\n",
    "        def dfs(i,pre):\n",
    "            if i == n:\n",
    "                check(pre)\n",
    "                return\n",
    "            dfs(i+1,pre)    \n",
    "            dfs(i+1,pre + [i])\n",
    "        dfs(0,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "\n",
    "        ans = [0] * (n-1)\n",
    "        def check(path):\n",
    "            vis = set()\n",
    "            res  = 0\n",
    "            for v in path:\n",
    "                if v in g:\n",
    "                    def dp(u):\n",
    "                        nonlocal res\n",
    "                        vis.add(u)\n",
    "                        maxv = 0\n",
    "                        for v in g[u]:\n",
    "                            if v not in vis and v in path:\n",
    "                                cur = dp(v) + 1\n",
    "                                res = max(res, maxv + cur)\n",
    "                                maxv = max(maxv, cur)\n",
    "                        return maxv\n",
    "                    dp(v)\n",
    "                    break\n",
    "            if res and vis == set(path):\n",
    "                ans[res-1] +=1\n",
    "            \n",
    "\n",
    "        def dfs(i,path):    \n",
    "            if i==n:\n",
    "                check(path)\n",
    "                return\n",
    "            dfs(i+1,path)\n",
    "            dfs(i+1, path + [i])\n",
    "        dfs(0,[])\n",
    "        return ans\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ans = [0]*(n-1)\n",
    "        g = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "\n",
    "        def check(path):\n",
    "            if not path:\n",
    "                return\n",
    "            res = 0\n",
    "            vis = set()\n",
    "            def dfs(u):\n",
    "                vis.add(u)\n",
    "                maxv = 0\n",
    "                nonlocal res\n",
    "                for v in g[u]:\n",
    "                    if v not in vis and v in path:\n",
    "                        cur = dfs(v)\n",
    "                        res = max(res, maxv + cur + 1)\n",
    "                        maxv = max(maxv, cur)\n",
    "                return maxv + 1\n",
    "                        \n",
    "            dfs(path[0])\n",
    "            dm = res -1\n",
    "            if dm-1 >=0 and vis == set(path):\n",
    "                ans[dm-1] +=1\n",
    "        def f(i, pre):\n",
    "            if i == n:\n",
    "                check(pre)\n",
    "                return\n",
    "            f(i+1,pre)\n",
    "            f(i+1,pre+ [i])\n",
    "        f(0,[])\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        ans = [0] * (n-1)\n",
    "\n",
    "\n",
    "        def check(path):\n",
    "            m = len(path)\n",
    "            res = 1\n",
    "            vis = set()\n",
    "            def dfs(u):\n",
    "                vis.add(u)\n",
    "                maxv = 0\n",
    "                nonlocal res\n",
    "                for v in g[u]:\n",
    "                    if v not in vis and v in path:\n",
    "                        cur = dfs(v)\n",
    "                        res = max(res, maxv + cur + 1)\n",
    "                        maxv = max(maxv, cur)\n",
    "                return maxv + 1\n",
    "            if not path:\n",
    "                return\n",
    "            dfs(path[0])\n",
    "            if res-1 >=1 and len(vis) == len(path):\n",
    "                ans[res-2] +=1\n",
    "                    \n",
    "        def f(i,pre):\n",
    "            if i==n:\n",
    "                check(pre)\n",
    "                return\n",
    "            f(i+1,pre)    \n",
    "            f(i+1, pre + [i])\n",
    "        f(0,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ans= [0] * (n-1)\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        def check(path):\n",
    "            vis = set()\n",
    "            dia = 1\n",
    "            def f(u):\n",
    "                vis.add(u)\n",
    "                maxv =0\n",
    "                for v in g[u]:\n",
    "                    if v not in vis and v in path:\n",
    "                        cur = f(v)\n",
    "                        nonlocal dia\n",
    "                        dia = max(dia, maxv + cur + 1)\n",
    "                        maxv = max(maxv, cur)\n",
    "                return maxv + 1\n",
    "            if path:\n",
    "                f(path[0])\n",
    "                if vis == set(path) and dia -1 >= 1:\n",
    "                    ans[dia-2] += 1\n",
    "\n",
    "\n",
    "        def dfs(i, pre):\n",
    "            if i==n:\n",
    "                check(pre)\n",
    "                return\n",
    "            dfs(i+1, pre)\n",
    "            dfs(i+1, pre+[i])\n",
    "        dfs(0,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            a -= 1\n",
    "            b -= 1\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "            \n",
    "        dist = [[0] * n for _ in range(n)]\n",
    "        ret = [0] * n\n",
    "        def subtree(node, fa):\n",
    "            son_states = []\n",
    "            for son in g[node]:\n",
    "                if son == fa:\n",
    "                    continue\n",
    "                ss = subtree(son, node)\n",
    "                son_states.append(ss)\n",
    "            all_state = []\n",
    "\n",
    "            def dfs(idx, state):\n",
    "                if idx == len(son_states):\n",
    "                    all_state.append(state)\n",
    "                    return\n",
    "                dfs(idx + 1, state)\n",
    "                for s in son_states[idx]:\n",
    "                    dfs(idx + 1, state | s)\n",
    "\n",
    "            dfs(0, 1 << node)\n",
    "            for mask in all_state:\n",
    "                nodes = []\n",
    "                d = 0\n",
    "                for j in range(n):\n",
    "                    if mask & 1 << j:\n",
    "                        for k in nodes:\n",
    "                            d = max(d, dist[j][k])\n",
    "                        nodes.append(j)\n",
    "                ret[d] += 1\n",
    "            return all_state\n",
    "        \n",
    "        def dfs(node, fa, dep, state):\n",
    "            dep += 1\n",
    "            for son in g[node]:\n",
    "                if son == fa:\n",
    "                    continue\n",
    "                dist[NODE][son] = dist[son][NODE] = dep\n",
    "                dfs(son, node, dep, state | 1 << son)\n",
    "        for NODE in range(n):\n",
    "            dfs(NODE, -1, 0, 1 << NODE)\n",
    "        subtree(0, -1)\n",
    "        return ret[1:]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
